#include <tr1/unordered_map>
#include "list_ss.cpp"
#include <iterator>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <sstream>
#include <ostream>
#include <fstream>
#include <assert.h>
#include <tuple>

typedef unordered_map<int, EL*> INT_EL_MAP;


void to_cerr(string msg) {
	//cerr << msg << endl;
}

template<typename T, size_t N>
size_t getSize(T (&)[N]) {
	return N;
}

class streamsummary {
private:
	INT_EL_MAP elements;
	int k;
	BUCKET * min;

public:
	streamsummary(int k) {
		this->k = k;
		this->elements = INT_EL_MAP();
		this->min = NULL;
	}

	~streamsummary() {
	}

	string to_string() {
		BUCKET * tmp = (*min).next;
		stringstream out;
		out << (*min).to_string() << "\n";

		while (tmp != min) {
			out << (*tmp).to_string() << "\n";
			tmp = (*tmp).next;
		}
		return out.str();
	}

	int get_size() {
		return this->elements.size();
	}

	void insert(int key) {
		//cerr << "insert: " << key << endl;
		if (this->elements.find(key) != this->elements.end()) {
			EL * _el = elements.find(key)->second;
			BUCKET * parent = (*_el).parent;
			BUCKET * next = (*parent).next;
			VECTOR_LIST result = (*parent).remove(_el);

			//cerr << "(" << (*result.front()).count << "," << (*result.back()).count << "," << (*parent).isEmpty() << ")" << endl;

			if ((*next).count == ((*parent).count + 1)) {
				//cerr << "CASE:next bucket == +1" << endl;
				(*next).add(_el);
				(*next).set_prev(result.front());
				(*result.front()).set_next(next);
			} else {
				BUCKET * new_bucket = new BUCKET(result.front(), result.back(),
						(*parent).count + 1);
				//cerr << "CASE:creating new bucket: " << endl;
				//cerr << "min.next: " << (*(*min).next).count << endl;
				(*new_bucket).add(_el);
				(*(*new_bucket).prev).set_next(new_bucket);
				(*(*new_bucket).next).set_prev(new_bucket);
				//cerr << "min.next: " << (*(*min).next).count << endl;

				////cerr << "created new bucket and updated prev and next" << endl;
			}

			if ((*parent).isEmpty()) {
				if (this->min == parent) {
					//cerr << "update min" << endl;
					this->min = (*(*min).prev).next;
				}
				delete parent;
			}

		} else if (this->elements.size() < this->k) {
			//cerr << "CASE:element not monitored. size < k " << endl;
			////cerr << "#elem" << ((min) == NULL)<< endl;

			EL * element = new EL(key);
			////cerr << "created EL: " << (*element).element << endl;

			if (this->min == NULL) {
				BUCKET * bucket = new BUCKET(NULL, NULL); // Create initial bucket
				(*bucket).add(element);
				this->min = bucket;
				//cerr << "min == null. CREATED Initial bucket. Count: " << (*min).count << endl;

			} else if ((*min).count == 1) {
				//to_cerr("min bucket.count == 1: ");
				(*min).add(element);
				////cerr << "parent count:" << (*(*element).parent).count << endl;
			} else {
				//cerr << "CASE: creating new min bucket" << endl;
				BUCKET * bucket = new BUCKET((*min).prev, min);
				(*bucket).add(element);
				(*min).set_prev(bucket);
				(*(*min).prev).set_next(bucket);
				this->min = bucket;
			}
			this->elements.insert(pair<int, EL*>(key, element));
		} else {
			to_cerr("CASE:element not monitored. replacing min element");

			//cerr << "elements in min: " << (*min).to_string() << endl;
			//cerr << "elements in elemensts" << endl;
			for (INT_EL_MAP::iterator it = elements.begin();
					it != elements.end(); it++) {
				//cerr << it->first << ",";
			}
			//cerr << endl;

			TUPLE_LIST_EL result = (*min).replace_min();
			BUCKET * prev = std::get < 0 > (result);
			BUCKET * next = std::get < 1 > (result);
			EL * old = std::get < 2 > (result);
			EL * element = new EL(key, (*min).count);

			if ((*min).count + 1 == (*(*min).next).count) {
				(*next).add(element);
				(*next).set_prev(prev);
				(*prev).set_next(next);
			}
			else {
				BUCKET * new_bucket = new BUCKET(prev, next, (*min).count+1);
				(*new_bucket).add(element);
				(*next).set_prev(new_bucket);
				(*prev).set_next(new_bucket);

			}

			if ((*min).isEmpty()) {
				BUCKET * new_min = (*min).next;
				delete min;
				min = new_min;
			}

			this->elements.erase((*old).element);
			delete old;
			this->elements.insert(pair<int, EL*>(key, element));
			//cerr << "elements in streamsummary.elements" << elements.size()<< endl;

		}
		//cerr << "end of insert\n###################" << endl;
	}
}
;

void test_zipf() {
	int n = 10;
	float alpha = 2.0;
	int num_values = 100;

	ifstream file;
	file.open("zipf.out", ifstream::in);
	////cerr << "fileopen" << endl;

	if (!file) {
		//cerr << "Could not open file: " << endl;

	}
	streamsummary ss(10);

	while (file.good()) {
		string num;
		getline(file, num);
		ss.insert(atoi(num.c_str()));
		//cerr << ss.to_string() << endl;
	}
	file.close();

	//cerr << "finished inserting" << endl;


	//cerr << ss.get_size() << endl;
}

//void test() {
//	BUCKET b = BUCKET(NULL, NULL);
//	BUCKET b2 = BUCKET(&b, &b);
//	b2.set_prev(&b);
//	b2.set_next(&b);
//
//	BUCKET * min = &b;
//
//	EL el1 = EL(1);
//	b.add(el1);
//	EL el2 = EL(2);
//	b.add(el2);
//	////cerr << b.get_elements().size() << endl;
//	b2.add(el1);
//	TUPLE_EL_EL_BOOL result = (*min).remove(&el1);
//	////cerr << b.get_elements().size() << endl;
//	////cerr << b2.get_elements().size() << endl;
//	////cerr << (*min).get_elements().size() << endl;
//	////cerr << (min == &b) << endl;

//unordered_map<int, EL*> mapp;
//
//	BUCKET b1 = BUCKET(NULL,NULL);
//	EL el = EL(3);
//	mapp.insert(pair<int, EL*>(3, &el));
//	b1.add(&el);
//
//	b1.remove(mapp.find(3)->second);
//
//	return 1;
//}

void test_file() {
	streamsummary ss(5);
	ifstream file;
	file.open("zipf.out", ifstream::in);
	if(!file) {
		//cerr << "Summary: Could not open file: " << endl;
		exit(1);
	}

	while (file.good())
	{
		string key;
		getline(file,key);
		ss.insert(atoi ( key.c_str() ));
	}
	file.close();

	cerr << ss.to_string() << endl;

	cerr << "elements in ss: " << ss.get_size() << endl;
}

int main() {

	test_file();

	return -1;

	//test_zipf();

//	int input [] = {1,2,2,3};
//
//	vector<int> vector_input;
//	for (int i = 0; i < GetArrLength(input); i++) {
//		vector_input.push_back(input[i]);
//	}
//
//	streamsummary ss(2);
//	for (int i = 0; i < vector_input.size(); i++) {
//		ss.insert(vector_input.at(i));
//		//cerr << ss.to_string() << endl;
//		//cerr << "*********************"<< endl;
//	}

	streamsummary ss(5);

	for (int i = 0; i < 50; i++) {
		ss.insert(i % 13);
		//cerr << ss.to_string() << endl;
	}
	//cerr << endl;

	//cerr << "elements in ss: " << ss.get_size() << endl;
	return -1;
}
